package com.lx.algorithm.temp;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-26 10:52:24
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-26     张李鑫                     1.0         1.0 Version
 */
public class GetMaxValue {

    /**
     * 给定一个整型数组arr，代表数值不同的纸牌排成一条线
     * 玩家A和玩家B依次拿走每张纸牌
     * 规定玩家A先拿，玩家B后拿
     * 但是每个玩家每次只能拿走最左或最右的纸牌
     * 玩家A和玩家B都绝顶聪明
     * 请返回最后获胜者的分数。
     *
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = { 5, 7, 4, 5, 8, 1, 6, 0, 3, 4, 6, 1, 7,5,6,7,4,2,1,444,53 };
        System.out.println(Math.max(before(arr, 0, arr.length - 1), after(arr, 0, arr.length - 1)));
        System.out.println(programming(arr));
    }


    /**
     * 先手出牌
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int before(int[] arr, int left, int right) {
        if (left == right) {
            return arr[left];
        }
        int p1 = arr[left] + after(arr, left + 1, right);
        int p2 = arr[right] + after(arr, left, right-1);
        return Math.max(p1, p2);
    }

    /**
     * 后手出牌
     *
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int after(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        int p1 = before(arr, left + 1, right);
        int p2 = before(arr, left, right - 1);
        return Math.min(p1, p2);
    }

    public static int programming(int[] arr) {
        int[][] beforeCache = new int[arr.length][arr.length];
        int[][] afterCache = new int[arr.length][arr.length];
        //先设置对角线的值从递归中可以看出 当左右相等的时候值就是arr[i]的值
        //后手不添加因为左右相等的时候就是0 数组创建的时候默认是0
        for (int i = 0; i < arr.length; i++) {
            beforeCache[i][i] = arr[i];
        }

        for (int i = 1; i < arr.length; i++) {
            int left = 0;
            int right = i;
            while (right < arr.length) {
                afterCache[left][right] = Math.min(beforeCache[left + 1][right], beforeCache[left][right - 1]);
                beforeCache[left][right] = Math.max(arr[left] + afterCache[left + 1][right], arr[right] + afterCache[left][right - 1]);
                left++;
                right++;
            }
        }
        return Math.max(beforeCache[0][arr.length - 1], afterCache[0][arr.length - 1]);
    }


}
